翻訳と辞書
Words near each other
・ Interxion
・ Interval (play)
・ Interval arithmetic
・ Interval boundary element method
・ Interval chromatic number of an ordered graph
・ Interval class
・ Interval contractor
・ Interval cycle
・ Interval edge coloring
・ Interval estimation
・ Interval exchange transformation
・ Interval finite element
・ Interval graph
・ Interval International
・ Interval Monday
Interval order
・ Interval propagation
・ Interval ratio
・ Interval recognition
・ Interval Research Corporation
・ Interval scheduling
・ Interval signal
・ Interval temporal logic
・ Interval training
・ Interval tree
・ Interval vector
・ Intervale
・ Intervale (Augusta County, Virginia)
・ Intervale Avenue (IRT White Plains Road Line)
・ Intervale Factory


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Interval order : ウィキペディア英語版
Interval order
In mathematics, especially order theory,
the interval order for a collection of intervals on the real line
is the partial order corresponding to their left-to-right precedence relation—one interval, ''I''1, being considered less than another, ''I''2, if ''I''1 is completely to the left of ''I''2.
More formally, a poset P = (X, \leq) is an interval order if and only if
there exists a bijection from X to a set of real intervals,
so x_i \mapsto (\ell_i, r_i) ,
such that for any x_i, x_j \in X we have
x_i < x_j in P exactly when r_i < \ell_j .
Such posets may be equivalently
characterized as those with no induced subposet isomorphic to the
pair of two element chains, the (2+2) free posets
.
The subclass of interval orders obtained by restricting the intervals to those of unit length, so they all have the form (\ell_i, \ell_i + 1), is precisely the semiorders.
The complement of the comparability graph of an interval order (X, ≤)
is the interval graph (X, \cap).
Interval orders should not be confused with the interval-containment orders, which are the containment orders on intervals on the real line (equivalently, the orders of dimension ≤ 2).
== Interval dimension ==

The interval dimension of a partial order can be defined as the minimal number of interval order extensions realizing this order, in a similar way to the definition of the order dimension which uses linear extensions. The interval dimension of an order is always less than its order dimension,〔http://page.math.tu-berlin.de/~felsner/Paper/Idim-dim.pdf p.2〕 but interval orders with high dimensions are known to exist. While the problem of determining the order dimension of general partial orders is known to be NP-complete, the complexity of determining the order dimension of an interval order is unknown.〔http://page.math.tu-berlin.de/~felsner/Paper/diss.pdf, p.47〕

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Interval order」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.